%% ---------------------------------------------------------------------
%% dyninsets.tex
%%
%% Created 2010-02-22 by Sohaib Ghani, Nathalie Henry-Riche, and
%% Niklas Elmqvist. 
%% 
%% Intended for submission to IEEE InfoVis 2010. (rejected)
%% Revised July-September 2010 for ACM CHI 2011.
%% ---------------------------------------------------------------------

%% ---------------------------------------------------------------------
%% Document class
%% ---------------------------------------------------------------------
\documentclass{chi2010pubsformat}

%% ---------------------------------------------------------------------
%% Packages
%% ---------------------------------------------------------------------

%% Times fonts
\usepackage{times}

% Permits inclusion of PNG, JPG, and PDF files under pdflatex
\usepackage{graphicx}

% Arabic page numbers for submission. (eliminate for camera-ready)
\pagenumbering{arabic}

% Mathematical symbols
\usepackage{mathptmx}
\usepackage{amssymb}

%% Use this for zero \parindent and non-zero \parskip, intelligently.
\usepackage{parskip}

%% Package to allow for subfigures
\usepackage{subfigure}

% For color backgrounds in tables
\usepackage{color}

% Prevents words from sticking out in the margin
\tolerance=5000

%% URLs
\usepackage{url}

%% NAT's Shortcuts
\newcommand{\BG}{Bring \& Go}
\newcommand{\DI}{Dynamic Insets}

%% ---------------------------------------------------------------------
%% Title, author(s), and affiliations
%% ---------------------------------------------------------------------

% Paper title
\title{Dynamic Insets for Context-Aware Graph Navigation}

% List of authors and affiliations
%\numberofauthors{3}

%% \author{
%%   \alignauthor Sohaib Ghani\\
%%   \affaddr{Purdue University}\\
%%   \affaddr{West Lafayette, IN, USA}\\
%%   \email{sghani@purdue.edu}
%%   \alignauthor Nathalie Henry Riche\\
%%   \affaddr{Microsoft Research}\\
%%   \affaddr{Redmond, WA, USA}
%%   \email{nathalie.henry@microsoft.com}\\
%%   \alignauthor Niklas Elmqvist\\
%%   \affaddr{Purdue University}\\
%%   \affaddr{West Lafayette, IN, USA}\\
%%   \email{elm@purdue.edu}
%% }

%% For anonymous submission, uncomment the below:
\numberofauthors{1}
\author{
   \alignauthor Anonymous author(s)\\
   \affaddr{Undisclosed institution(s)}\\
   \affaddr{Undisclosed location(s)}\\
   \affaddr{Undisclosed e-mail address(es)}
}

% Get rid of this line for camera-ready version (if applicable)
\toappear{Submitted to ACM CHI 2011.  Please do not redistribute.}

% Teaser figure goes here
\teaser{
  \resizebox{\textwidth}{!}{\includegraphics{figures/map-chicago}}
  \caption{The Dynamic Insets technique for a map of the Chicago area
    showing insets for off-screen nodes with their surrounding
    context.}
  \label{fig:dynamic-insets}
}

%% ---------------------------------------------------------------------
%% Document Beginning
%% ---------------------------------------------------------------------
\begin{document}

\maketitle

% ----------------------------------------------------------------------
% Abstract
% ----------------------------------------------------------------------
\abstract{Utilizing both overview and detail while navigating in
  graphs, for example road networks, social networks, or airline
  routes, is difficult.
  Common navigation techniques such as pan, zoom, and bird's eye views
  are often tedious and cumbersome to use, especially when objects of
  interest are located far apart.  
  We present a navigation technique called Dynamic Insets that
  provides context awareness for graph navigation.
  Dynamic insets utilize the topological structure of the network to
  draw a visual inset for off-screen nodes that shows a portion of the
  surrounding area for the destinations of links leaving the edge of
  the screen.  
  We implement and discuss the use of dynamic insets for general graph
  navigation as well as geographical maps and social networks.
  We also present results from a set of user studies that show that
  our technique is significantly more efficient than existing
  techniques for graph navigation in different networks.}

%% ACM Computing Review (CR) categories.
%% See <http://www.acm.org/class/1998/> for details.
\category{H.5.2}{Information Interfaces and Presentation}{User
  Interfaces}---\textit{Interaction styles}
\category{I.3.6}{Computer Graphics}{Methodology and
  Techniques}---\textit{Interaction techniques}

%% Keywords that describe your work.
\keywords{Node-link, topology-aware navigation,
  focus+context, DOI.}

%, degree-of-interest, interaction, evaluation.}

% ----------------------------------------------------------------------
% Body
% ----------------------------------------------------------------------
\section{Introduction}

Interacting with road networks in a handheld GPS or on map websites
such as Google Maps or Bing Maps is just one example of large-scale
networks that lots of people use in their everyday life, and there are
many other examples of more specialized applications for social
network analysis, network topology design, and general graphs.
Navigation in these networks is usually performed using a sequence of
pan and zoom operations~\cite{Furnas1995}, sometimes with a bird's eye
view.
For example, to move from one position in a large network to another
position far away, the common approach is to zoom out, pan to that
position, and finally zoom in~\cite{vanWijk2003}.  
However, this can be tedious, ineffective, and even
disorienting~\cite{Furnas1986, Furnas1995}.

A recent trend in graph navigation is to utilize the topology of a
graph to enhance navigation; examples include link sliding and Bring
\& Go~\cite{Moscovich2009}.
However, these techniques do not provide an awareness of the context
around destination nodes, context that is useful when deciding where
to go next.

In this paper, we present a technique called \textit{Dynamic Insets}
that supports multi-focus interaction during navigation in graphs.
Drawing inspiration from cartography, we add dynamic map insets that
show a small part of the surrounding area for the destinations of
links leaving the boundary of the screen
(Figure~\ref{fig:dynamic-insets}).  
Insets can be clicked to automatically animate the user's viewpoint to
that destination.
We also introduce interest functions that control which off-screen
nodes should be made visible through insets.  
By choosing between different interest functions, the user could opt
to show all neighboring nodes, or filter to show only nearby gas
stations (for a map application), central actors (for a social
network), or access points (for network topology design).

Effective graph navigation techniques are essential for managing the
large graphs that are common to many HCI
applications~\cite{Herman2000}.
To validate the new technique, we also perform a controlled experiment
involving human subjects where we compare it to the Bring \& Go
technique of Moscovich et al.~\cite{Moscovich2009}.  
Our results show that our technique significantly helps users in
maintaining an awareness of both details as well as the overview of
the network.
We follow up with two usability studies where we apply the dynamic
insets technique to social networks and geographic maps.
Our findings here suggest that the technique also scales to larger
graphs, and that it does not interfere with mental map creation.

This paper is structured as follows: We first survey the related work.  
We then present the dynamic insets technique.  
We describe a controlled user study where we compare the technique to
Bring \& Go~\cite{Moscovich2009}.  
We present and discuss our results.
We then present our examples, including results from the
usability studies we conducted for these.
We close with a summary and our plans for future work.

%% ---------------------------------------------------------------------
%% RELATED WORK
%% ---------------------------------------------------------------------
\section{Related Work}

In their survey on graph visualization, Herman et
al.~\cite{Herman2000} emphasize navigation and interaction techniques
as essential for understanding large graphs.
Here we review relevant work on general navigation, off-screen
awareness and navigation, and specific navigation techniques for
graphs.

\subsection{Common Navigation Techniques}

\paragraph{Scrolling} 

Scrolling is the standard method for navigating in visual spaces.
However, scrolling interfaces may become cumbersome when the space to
explore is too large.  
Multiple improvements address this, such as adjusting the level of
zoom from the scrolling speed (SDAZ)~\cite{Igarashi2000}, or taking
advantage of the context to optimize scrolling direction, speed, and
zoom level~\cite{Ishak2006}. 
However, to inspect a large 2D workspace, scrolling still requires
considerable effort from the user.

\paragraph{Pan and Zoom}

Pan and zoom are commonly used navigation techniques in many
applications.
Since the original infinitely zoomable canvas proposed in
Pad~\cite{Perlin1993}, there has been a large amount of work in this
area. 
Furnas and Bederson~\cite{Furnas1995} designed a space-scale formalism
for describing and understanding pan and zoom interactions.
Multiple studies show that combining zooming and panning is more
efficient than panning~\cite{Furnas1995, vanWijk2003}. 
However, pan and zoom may become tedious for distant objects in
large spaces~\cite{Furnas1986}.  
More importantly, this technique may frustrate users when navigating
in graphs as the destination is often known (the other end of the
link) but these techniques do not take advantage of that information.

\paragraph{Split Screens}

Splitting the viewport (screen) into subviewports is another standard method
for large visual spaces, and gives the user awareness of multiple,
possibly distant, regions of the space.
Shoemaker and Gutwin~\cite{Shoemaker2007} present a technique that
automatically splits the viewport when the pointer moves sufficiently
far from the focus.
However, the main disadvantage of split-screen techniques is loss
of intervening context~\cite{Elmqvist2008}.

\paragraph{Overview+Detail}

Overview and detail techniques use multiple windows to present the
overview of the whole workspace as well as the current region in
focus. 
The overview often includes a visual cue indicating the current
viewport.
This marker may be moved by the user to navigate to other region of
the space.
Hornbaek and Frokjaer~\cite{Hornbaek2001} showed that overview and
detail techniques are easy to use and can outperform panning and
fisheye views for some tasks. 
While these techniques have been shown to be effective in navigating
large networks~\cite{Hornbaek2002, Kaptelinin1995}, additional
interaction is required to manage the windows. 
Users have to perform a series of inspections in the overview to
locate possible regions of interest. 
As overviews often occupy small screen space, the large
scaling factor becomes a hindrance in finding specific landmarks or
follow given elements such as links. 
Thus, the technique may degrade the overall experience as users
randomly move the visual cue of the viewport to find the region of
interest.

\paragraph{Space Distortion Techniques}

Space distortion may be effective for navigating in large spaces.  
Techniques such as fisheye views~\cite{Furnas1986} magnify
the focus region while the surrounding context is shown in less
detail.  
Rubber sheet stretching~\cite{Sarkar1993} is another model of
distorting 2D space. 
In this model, the space is stretched at the focus
point for navigation and context awareness.  
Elmqvist et al.~\cite{Elmqvist2008} give a space-folding technique
called M\'{e}lange that combines different parts of the visual space
so that multiple focus points and as much as possible of their
surrounding context are visible on the screen.
Other work show that distortion techniques can be efficient for
navigating in large networks~\cite{Schaffer1996} or for large steering
tasks~\cite{Gutwin2003}. 
However, space distortion suffers from a number of issues: the
transition between focus and context needs to be carefully
designed~\cite{Pietriga2008}, fisheyes may cause problems for
targeting tasks~\cite{Gutwin2002}, and Hornbaek et
al.~\cite{Hornbaek2001} showed that performance may be lower
compared to overview+detail techniques.

\subsection{Navigation to Off-Screen Targets}

\paragraph{Visual Cues} 

Some techniques have been specifically designed to provide
awareness of off-screen targets.
Halo~\cite{Baudisch2003}, and its descendants
Wedge~\cite{Gustafson2008} and EdgeRadar~\cite{Gustafson2007},
indicate off-screen targets by adding visual cues to the border of the
viewport.
While these techniques give users awareness of off-screen targets,
they do not provide a mechanism to reach them.

\paragraph{Proxies}

Proxy-based techniques provide local copies of distant or off-screen
targets to ease their selection. 
Drag-and-pop~\cite{Baudisch2003b} and Vacuum~\cite{Bezerianos2005} are
good examples of such techniques. 
As these techniques are primarily designed for selection rather than
navigation, they do not provide the context of targets, forcing
users to visit each of them to see the context.

\paragraph{Proxies+Context} 

One of the most relevant techniques to ours is
WinHop~\cite{Partridge2007}, which introduces an inset window to let
users explore the distant region without actually leaving the current
location. 
However, WinHop does not take advantage of the network topology, so
the user must first select the node to expand.
This may also affect its ability to scale to large visual spaces.

\begin{figure*}[tbh]
  \centering
  \resizebox{\textwidth}{!}{\includegraphics{figures/dyninsets-idea}}
  \caption{Dynamic construction of insets for a simple graph
    consisting of 7 nodes and 8 edges.  A is the source node ($n_s$).}
  \label{fig:dyninsets-idea}
\end{figure*}

\subsection{Navigation in Networks}

\paragraph{Distortion Lenses} 

A few distortion techniques have been specifically designed for
graphs. 
EdgeLens~\cite{Wong2003} interactively distorts links around the focus
point to remove potential clutter. 
A work more related to our technique is the Bring-Neighbor
Lens~\cite{Tominski2006}, a lens that temporarily modifies the graph
layout to show all neighbors of the node in focus. 
However, this distortion lens has not been designed for navigation:
users can gain awareness of the neighbors, but are still required to
use a navigation technique such as pan and zoom to reach them.

\paragraph{Degree-of-Interest Techniques}

Furnas~\cite{Furnas1986} showed that the visibility of
graph features can be controlled by the user through a degree of
interest (DOI) function.  
Nodes are ranked according to their topological distance to the focus
node in the graph.  
The graph may then be distorted to show the most interesting
information to the user. 
This principle has been employed for hierarchies~\cite{Plaisant2002}
and in large networks~\cite{Gansner2005, vanHam2009}. 
However, these techniques deform the graph, compromising the user's
mental map.

\paragraph{Topology-aware Navigation}

Moscovich et al.~\cite{Moscovich2009} presented two navigation
techniques taking advantages of the topology information of the
network to ease navigation.
Their first technique, Link Sliding, provides guided panning and
zooming when continuously dragging along a link. 
The second technique, Bring \& Go, gathers the neighbors of a node of
interest and enables the user to navigate to one of these at a time,
animating the view to its original position. 
These techniques have been compared to overview+detail and pan and
zoom techniques.
Bring \& Go outperformed both of these, while Link Sliding had mixed
results. 
Regardless, from all the techniques presented in this section, these
are most relevant to ours. 
We designed dynamic insets to overcome the principal drawback of Bring
\& Go: the lack of context for off-screen targets, requiring 
navigation to see the context.

%% ---------------------------------------------------------------------
%% DYNAMIC INSETS
%% ---------------------------------------------------------------------
\section{Dynamic Insets}

Dynamic Insets is a topology-aware navigation technique for providing
context awareness while traversing large-scale networks.
It uses the connectivity of the graph to bring off-screen neighbors of
on-screen nodes---and their context---into the viewport as insets
(Figure~\ref{fig:dynamic-insets}).
In this way, multiple destinations for visual links leaving the edge
of the screen can be explored without actually leaving the current
location; this is more generally known as \textit{multi-focus
  interaction}~\cite{Elmqvist2008}.
The insets are created by cutting out a region of the visual space
surrounding the off-screen neighboring nodes and bringing these
regions into the main viewport as small, nested viewports.
Figure~\ref{fig:dyninsets-idea} shows the basic idea, where a simple
network with three off-screen nodes of interest are shown on
the screen using dynamically created insets.

While the above description captures the essence of the dynamic insets
technique, there exist several details concerning \textit{which}
off-screen nodes to include, how insets are created, how they are laid
out, and how to display distance information using the technique. 
We discuss these issues below.

\subsection{Degree-of-Interest Function}

Instead of trying to visualize \textit{all} off-screen targets, such
as existing off-screen navigation techniques~\cite{Partridge2007},
dynamic insets uses the connectivity of the graph itself to determine
\textit{which} off-screen targets to include.
This means that the technique can handle even very large graphs. 

To give additional expressive power to the technique, we use the
concept of a \textit{degree-of-interest (DOI)
  function}~\cite{Furnas1986} to rank all off-screen nodes
in terms of their interest for a particular task.
The simplest imaginable DOI function is a binary one that uses a
neighbor relation between the set of visible nodes $V$ and an
off-screen node $n$:
$$
DOI(n, V)  = 
\left\{
\begin{array}{lr}
1 & \exists v \in V : \mathrm{neighbor}(n, v)\\
0 &  \mathrm{otherwise}
\end{array}
\right.$$

In other words, this function will assign 1 to all neighbors of
currently visible nodes, and 0 to all others. 
An important special case for this situation is where the user has
selected a particular source node $n_s$ to use as a focus point
(instead of all currently visible nodes).  
The above DOI function can be trivially adapted for this purpose by
passing $V = \{ n_s \}$.

Given any DOI function of the above format, we rank all off-screen
nodes according to their current DOI values.
A certain number of the highest ranked off-screen nodes will be
selected depending on the number of dynamic insets to create.
Ties may be arbitrarily broken, for example using distance, so that
nearby nodes are given precedence over more distant ones.  
However, a better approach is to devise a modified DOI function that
takes distance into account:
$$DOI_{dist}(n, V) \:=  DOI(n, V) / \mathrm{dist}(n)$$
where dist$(n)$ is the distance from $n$ to the edge of the screen.

The default setting for our technique is to use the standard DOI
function defined above, but to allow the user to select a focused
source node $n_s$ by clicking on it.
Clicking outside any node on the visual space will clear the current
source node and return to the default setting.

In addition, more esoteric interest functions are also possible,
including interest functions composed of several simpler interest
functions, or which make use of domain-specific information.
Here follows examples of such DOI functions:

\begin{itemize}
\item For a GPS, interests could be assigned for nearby gas
  stations, shopping malls, or hospitals, weighted by distance;
\item For airline route selection (such as the Delta Air Lines Route
  Map\footnote{\url{http://delta.innosked.com/}}), destinations could
  be ranked according to their ticket price, travel duration, or
  number of stops; and
\item For social network analysis, the interest of off-screen
  neighbors could be based on the connection strength.
\end{itemize}

\subsection{Insets}

Given that we have derived \textit{which} off-screen nodes to make
visible on the screen, the next step is to actually create the insets.
Insets are small rectangular regions containing the target node and
its surrounding context in the visual space.
They have a visual border to differentiate them from the main
viewport, and they are laid out on the edge of the screen to coincide
where the link they are associated with leaves the main viewport (if
possible, see the next section).

Figure~\ref{fig:dyninsets-idea}(c) shows the inset for three
off-screen nodes in a simple graph. 
Insets are not static, but the viewport in each inset area can be
interacted with, such as panning or zooming in and out (left-dragging
and using the mouse wheel in our implementation, respectively).
Clicking an inset will animate the position of the user's viewport to
the location of the target node in the inset.
This both provides a quick way of navigating in the graph, and also
makes the path from source to destination clearly visible to the user,
thereby reinforcing their awareness of the entire visual space.

\subsection{Inset Layout}

We have designed a simple layout algorithm for positioning insets
along the edge of the screen. 
It has two constraints:

\begin{itemize}

\item\textbf{Align insets with their links.} Insets should be placed
  so that their location on the edge of the screen coincides with the
  outgoing visual link that it is associated with.
  Ideally, the visual link on the main viewport and on the inset
  viewport should align perfectly to maximize the visual connection
  (all three insets in Figure~\ref{fig:dyninsets-idea}(c) exhibit this
  property).

\item\textbf{Avoid total occlusion.} For situations with many outgoing
  links, insets may start to overlap.
  This is acceptable as long as no single inset is fully occluded by
  another.

\end{itemize}

For overlapped insets, the algorithm accordingly stacks the insets as
shown in Figure~\ref{fig:paging}.  
We also implement a paging interaction technique similar to that in
the M{\'e}lange technique~\cite{Elmqvist2008}, where the user can
hover the mouse cursor over an inset to bring it to the top.

\begin{figure}[htb]
  \centering
  \resizebox{\columnwidth}{!}{\includegraphics{figures/flipping}}
  \caption{Insets that overlap in space are stacked so that all insets
    are at least partly visible.
    This allows them to be paged through by hovering the mouse cursor
    over the visible part, bringing it to the top.}
  \label{fig:paging}
\end{figure}

\subsection{Drag-to-Fan}

Sometimes paging between insets is not sufficient if the number of
stacked insets is very high, such as for a central actor in a social
network with a degree in the hundreds or thousands.
We propose the \textit{drag-to-fan} technique
(Figure~\ref{fig:drag-to-fan}) to support this situation, where the
user can separate (fan out) stacked insets by dragging the mouse on an
inset stack.
The mouse cursor then controls the radius of a semi-circle whose
perimeter will be used to space out the stacked insets.
The inset stack essentially becomes a pie menu, and users can
themselves control how far they have to displace insets to be able to
see the desired destination.

Accordingly, selecting an inset using drag-to-fan is done by ``dialing
in'' the inset, i.e., through the angle between the pointer and the
original click.
What happens when releasing the button is configurable: the
straightforward approach is that this means travel to the inset, just
like clicking on an inset.
However, because this does not allow users to cancel the travel
operation if they do not find the inset they are looking for in the
stack, our implementation just changes the stacking order to bring the
selected node to the top of the stack.

\begin{figure}[tbh]
  \centering
  \resizebox{\columnwidth}{!}{\includegraphics{figures/drag-to-fan}}
  \caption{Interaction sequence for the drag-to-fan technique.
    The user presses and holds the mouse button on an inset, then
    drags to fan the insets along the perimeter of a semi-circle.
    Releasing the button over an inset will execute the configured
    action (travel to, bring to top, etc).}
  \label{fig:drag-to-fan}
\end{figure}

\subsection{Distance Awareness}
\label{sec:distance}

Our new technique does not naturally support distance awareness in its
visual representation such as, for instance, Bring \&
Go~\cite{Moscovich2009}.
Nevertheless, we can easily extend the representation of individual
insets to incorporate this information.
Here are a few different alternatives:

\begin{itemize}

\item\textbf{Number:} The simplest approach is to add a number for the
  distance from the edge of the screen to the destination node shown
  in the inset (Figure~\ref{fig:distvis}(a)).  
  We use this method.

\item\textbf{Border Color:} A color scale (i.e., a heatmap) can be
  used for the inset border to convey distance
  (Figure~\ref{fig:distvis}(b)).

\item\textbf{Transparency:} Changing the inset transparency: distant
  nodes are translucent, nearby ones opaque
  (Figure~\ref{fig:distvis}(c)).

\item\textbf{Size:} Scaling the size of the inset so that distant
  destinations are smaller than nearby ones
  (Figure~\ref{fig:distvis}(d)).

\item\textbf{Overview map:} This could show both the extents of the
  main viewport as well as the actual position of each inset.

\end{itemize}

\begin{figure}[htb]
  \centering
  \resizebox{\columnwidth}{!}{\includegraphics{figures/distvis}}
  \caption{Four alternatives for distance visualization: (a) actual
    number, (b) border color scale, (c) inset transparency, and (d)
    inset size.}
  \label{fig:distvis}
\end{figure}

\subsection{Implementation Notes}

We have implemented dynamic insets in a graph visualization built
using Java and the Piccolo toolkit.
Our algorithm first calculates DOI values for all off-screen nodes and
ranks them using a priority queue. 
Given a specific budget $N$ of the maximum number of insets to
display, the $N$ most highly-ranked off-screen nodes are selected and
cameras are placed at their locations.
A layout algorithm tries to optimize the location of the insets
associated with each camera on the screen border.
This algorithm will first strive to preserve link alignment, but,
failing that, will stack overlapping insets to ensure that no inset is
fully occluded.
If there are two insets for the same node but for different links, the
layout algorithm will combine these insets if they are located within a
specific distance of each other on the canvas.
  
%% ---------------------------------------------------------------------
%% USER STUDY
%% ---------------------------------------------------------------------
\section{Controlled Experiment}

We conducted a study to validate that the dynamic insets technique
does provide efficient graph navigation.
Here we describe our methods, present the results, and discuss them.

%-------------------------------------------------------------------------
\subsection{Method}

\subsubsection{Participants and Apparatus}

We recruited 12 participants balanced for age and gender, and screened
to not be color-blind. 
All participants indicated that they used computers more than 16
hours/week. 
The participant pool consisted of 6 males and 6 females, with ages
ranging from 22 to 47.  
Each participant used a 3.00 GHz dual-core PC with 4 GB of memory,
running Microsoft Windows Vista, and equipped with a 21'' flat-screen
monitor set to a resolution of 1600$\times$1200.  
The size of the viewport was set to 1000$\times$1000 pixels.

\subsubsection{Techniques}

We used our \DI\ (DI) technique as described in this paper.
Drag-to-fan was disabled to minimize extra interaction.
Moscovich et al.~\cite{Moscovich2009} showed that navigation
techniques taking advantage of graph topology outperforms traditional
techniques such as pan and zoom, and bird's eye views.
In particular, the \BG\ (BG) technique presented in that paper
outperformed all other techniques.
Thus, we decided to compare our technique to \BG.

We reimplemented \BG, using standard values for the animation speed
for bringing neighbors (500ms) and for traveling to destinations
(600ms).

\subsubsection{Tasks}

We used the first task proposed by Moscovich et
al.~\cite{Moscovich2009} since it captures awareness of direct
neighbors.
We also included two additional tasks to capture context awareness:

\begin{description}
 \item[CN]\textbf{CountNeighbors.}  How many neighbors of the node
   named ``cat'' are vegetables?
 \item[CC]\textbf{CloseContext.} Which neighbor of the ``cat'' node is
   enclosed by a \textbf{red} circle?
   (The circle diameter is small enough to be fully visible in the
   insets.)
 \item[DC]\textbf{DistantContext.} Which neighbor of the ``cat'' node
   is enclosed by a \textbf{red} circle?
   (The circle diameter is larger than the size of the insets.)
\end{description}

We included two different context tasks to force participants to have
to zoom and pan the insets in the DI condition.
We wanted to investigate whether this extra interaction would cause
the technique to exhibit worse performance than BG.

\subsubsection{Datasets}

To measure the performance of the techniques in realistic conditions,
we selected two datasets with two densities: sparse vs.\ dense.
To allow us to strictly control the network topology, we did
not generate complete graphs, but only a subset of those nodes and
edges involved in a particular task.
This also allows us to keep the experiment to a reasonable length and
limit user fatigue and frustration (potentially induced by visiting a
very large number of neighbors).

To achieve this, our graphs had a star structure with the source node,
labeled ``cat'', at the center of the star.  We then created 20
potential destination nodes as neighbors to ``cat'' (level 1), each in
turn having an additional four local neighbors (level 2).  Thus, we
had a total of 101 nodes and 100 edges.  All level 1 neighbors were
located at random distances from the source node, but sufficiently
distant to be outside of the viewport when viewing the source ``cat''
node at default magnification level (pan and zoom was disabled).
Level 2 neighbors were arranged equidistantly in a circle around their
level 1 parent---the size of this circle was small enough to fit
inside the insets for the CC task, whereas it was larger than the
insets for the DC task.

To achieve different graph densities, we varied only the concentration
of the destination nodes (level 1) in space:

\begin{itemize}
\item\textbf{Sparse.} Neighbors are equally distributed in a circle
  around the source node (Figure~\ref{fig:socnet-sparse}).
\item\textbf{Dense.} Neighbors are placed in a $90^{\circ}$ arc
  centered around the horizontal to the right of the source
  (Figure~\ref{fig:socnet-dense}).
\end{itemize}

This strategy lets us keep the number of neighbors to visit stable
while reproducing the artifacts induced by both sparse and dense
graphs.
More specifically, the dense case causes high overlap for insets that
mimics a large graph without penalizing the BG technique.
For the DI technique, however, users will be forced to page between
insets to find the correct target.
Again, we wanted to investigate whether this extra interaction would
impact the performance of the DI technique.

\begin{figure}[htb]
  \centering
  \subfigure[Social network used in the experiment (Sparse/CloseContext).]{
    \resizebox{\columnwidth}{0.7\columnwidth}{\includegraphics{figures/socnet-sparse}}
    \label{fig:socnet-sparse}
  }
  \subfigure[Social network used in the experiment (Dense/CloseContext).]{
    \resizebox{\columnwidth}{0.7\columnwidth}{\includegraphics{figures/socnet-dense}}
    \label{fig:socnet-dense}
  }
  \label{fig:socnet}
  \caption{Social network with the dynamic insets technique.}
\end{figure}

\subsubsection{Experimental Design}

Given the above factors, we used a within-subject
full-factorial design: 2 navigation techniques ($N$) $\times$ 2
densities ($D$) $\times$ 3 tasks ($T$) $\times$ 3 repetitions = 36
unique conditions.
We counterbalanced the order of the techniques.  
The order of the tasks was fixed whereas density factor was randomized
and graphs were randomly generated
for each trial, including the number of targets (for CN), and the
position of the red circle (for CC and DC).  
With 12 participants, we collected data for a total of 432 individual
trials.

\subsubsection{Procedure}

Participants received training before each technique and each task.
We ensured they answered correctly before performing the timed tasks.
For each trial, participants clicked on a button to indicate that they
had finished reading the description of the task and were ready to
begin, and pressed the space bar when they were done.  
The application recorded accuracy and completion time.  
The completion timer started only after each navigation technique had
been first activated (i.e., after the initial BG animation had ended).
We did not enforce any time limit.  
After the experiment, we collected user preferences and comments using
a questionnaire.  
The study lasted approximately one hour, including the initial
training session and the post-experimental questionnaire.

\subsubsection{Hypotheses}

\begin{description}
\item[H1] For CountNeighbors, DI will perform as well as BG for both
  correctness and completion time.
\item[H2] For CloseContext, DI will be faster than BG because
  there is no need to travel to a neighbor to see its context.
\item[H3] For DistantContext, DI will be faster than BG in the sparse
  graph because panning and zooming in each inset for DI is easy.
  However, for dense graphs, BG will be faster because the insets in
  DI overlap with each other, requiring additional interaction.
\end{description}

\subsection{Results}

We averaged measurements for all repetitions for each condition.
Below we discuss these results in more detail.

\subsubsection{Correctness}

Correctness was high: 97 \% across all tasks.
Table~\ref{tab:correctness-effects} summarizes the main effects on
correctness for all factors, analyzed using logistic regression.  
As the table shows, only Task $T$ had a significant effect.  
We studied this using a Tukey HSD, and found that the only significant
difference was that the CN task was less accurate than the
CC task ($|t| = 2.05, p = .04$).  
For the CN task, the mean correctness was 93 \% for both
navigation types with no significant difference between them ($F(1,
11) = .08, p = 0.78$).

\begin{table}[htb]
  \centering
  \begin{tabular}{|c|c|r|r|r|}
    \hline
    \textbf{Task} & 
    \textbf{Factors} & 
    \textbf{df, den} &
    \textbf{F} &
    \textbf{p}\\
    \hline\hline
    All & Navigation type (N) & 1, 11 & 0.08 &\\
    & Density (D) & 1, 11 & 0.08 & \\
    & Task (T) & 2, 22 & 3.36 & *\\
    \hline
  \end{tabular}\\
  ~* = $p \le 0.05$, ** = $p \le 0.001$.
  \caption{Effects of factors on correctness (logistic regression).}
  \label{tab:correctness-effects}
\end{table}

\subsubsection{Completion Time}

Table~\ref{tab:time-effects} summarizes the significant effects on
completion time using a repeated-measures analysis of variance
(RM-ANOVA).  
We found that the completion time violated the normality assumption of
the ANOVA, so we analyzed the logarithm of the times.
Other assumptions were met.  
Figure~\ref{fig:time} shows boxplots for the completion time as a
function of the navigation type $N$ and other factors.  
In particular, we analyzed the task factor $T$ using a Tukey HSD and
found that all pairwise differences were significant ($p < .001$) in
the order DC $>$ CN $>$ CC (decreasing time, CC was fastest).

\begin{table}[htb]
  \centering
  \begin{tabular}{|c|c|r|r|r|}
    \hline
    \textbf{Task} & 
    \textbf{Factors} & 
    \textbf{df, den} &
    \textbf{F} &
    \textbf{p}\\
    \hline\hline
    All & Navigation type (N) & 1, 11 & 205.37 & **\\
    & Density (D) & 1, 11 & 2.31 & \\
    & Task (T) & 2, 22 & 85.97 & **\\
    & V * T & 2, 22 & 229.75 & **\\
    & D * T & 2, 22 & 9.82 & **\\
    & V * D * T & 2, 22 & 3.46 & *\\
    \hline
    CN & Navigation type (N) & 1, 11 & 6.26 & **\\
    & Density (D) & 1, 11 & 1.92 & \\
    \hline
    CC & Navigation type (N) & 1, 11 & 559.58 & **\\
    & Density (D) & 1, 11 & 7.59 & *\\
    \hline
    DC & Navigation type (N) & 1, 11 & 34.93 & **\\
    & Density (D) & 1, 11 & 3.89 & \\
    \hline
  \end{tabular}\\
  ~* = $p \le 0.05$, ** = $p \le 0.001$.
  \caption{Effects of factors on time (RM-ANOVA).}
  \label{tab:time-effects}
\end{table}

\begin{figure*}[tbh]
  \centering
  \subfigure[All tasks combined.]{%
    \resizebox{0.32\textwidth}{!}{\includegraphics{plots/time-vis}}
    \label{fig:time-vis}
  }
  \subfigure[Task $T$.]{%
    \resizebox{0.32\textwidth}{!}{\includegraphics{plots/time-visxtask}}
    \label{fig:time-visxtask}
  }  
  \subfigure[Density $D$.]{%
    \resizebox{0.32\textwidth}{!}{\includegraphics{plots/time-visxdensity}}
    \label{fig:time-visxdensity}
  }
  \caption{Completion time as function of navigation type $N$ and
    the other experimental factors.}
  \label{fig:time}
\end{figure*}

\subsection{Discussion}

We can summarize our findings as follows:

\begin{itemize}
\item Bring \& Go is faster than dynamic insets for CountNeighbors,
  but not more accurate (partially confirming H1);
\item Dynamic insets are significantly faster than Bring \& Go for the
  CloseContext task (confirming H2); and
\item Dynamic insets are faster than Bring \& Go for the
  DistantContext task (partially confirming H3).
\end{itemize}

\subsubsection{Explaining the Results}

The results from our study obey our intuition, but there are some
surprises as well. 
Collectively, as we correctly hypothesized, dynamic insets are faster
than the Bring \& Go technique (Figure~\ref{fig:time-vis}). 
This is clearly an effect of the user being able to see the off-screen
nodes along with their context without the need to travel to each node.

However, the fact that dynamic insets were significantly slower than
Bring \& Go for the CountNeighbor task is a surprise
(Figure~\ref{fig:time-visxtask}); we had expected the techniques to be
comparable in time.
We think the reason for this effect is that users had more screen
space to cover for DI than for BG: for Bring \& Go, all neighbors are
grouped together close to the center node, whereas for dynamic insets,
the neighbors are spread out in insets placed around the edge of the
screen.
 
As hypothesized, dynamic insets are significantly faster than Bring \&
Go for the CC task (Figure~\ref{fig:time-visxtask}).  
According to the same figure, they are also faster for the DC task,
which we had not anticipated.
It seems that the benefit of being able to see the context surrounding
a node without having to travel there outweighs the extra interaction
needed to page between stacked insets in the dense case.
In fact, density had no significant impact on completion time
(Figure~\ref{fig:time-visxdensity}). 
While surprising, this shows that both Bring \& Go and dynamic insets
are robust against locally high node densities.

The post-questionnaire results also showed that all participants
preferred DI to BG. 
Most of them explained that BG required them to travel to the
neighbors' locations to assess the context, whereas the context was
easily accessible on the viewport using DI.  
Several participants stated that even with insets overlapping and the
need to use the zoom inside the inset, DI was still far less tedious
than BG.

\subsubsection{Limitations and Generalizations}

We were forced to make a large number of decisions on how to design
our controlled experiment.
For example, to keep the experiment at a reasonable length, we did not
include standard techniques such as pan and zoom, and bird's eye
views.  
We based this decision on Moscovich et al.'s~\cite{Moscovich2009}
study that demonstrated that the Bring \& Go technique outperformed
these. 
From our study results, we can conclude that dynamic insets outperform
Bring \& Go for all context-related tasks. 
Therefore, we can reasonably argue that dynamic insets outperform
standard techniques such as pan and zoom, or bird's eye views for
these tasks.  

However, further research is required to study how these
techniques help users maintain a mental map of the network.
For example, Bring \& Go distorts the network (potentially breaking
the users' mental map) but uses the layout of the neighbors brought to
maintain distance awareness. 
Dynamic insets do not distort the network but introduce visual
encodings for indicating the distance. 
It is difficult to evaluate the impact of these compromises, and
techniques such as pan and zoom may perform better here for
mental map building.

Another potential limitation is that our controlled experiment uses a
tree instead of a full graph.
Our motivation was that we wanted to study the canonical graph
navigation task, i.e., navigating from one node to another, and in
such situations, there is no need to model the full graph.
Also, we performed our experiment using a small network consisting of
only 101 nodes and 100 edges.
We argue that dynamic insets and Bring \& Go only act on local
sub-graphs and thus that the results found in our experiment are
generalizable to larger networks, particularly for small-world
networks~\cite{Watts1998} (such as social networks) that are locally
dense but globally sparse.
Finally, in the dense case we do not increase the number of neighbors
but only their spatial arrangement (all to one side of the starting
node).
The reason for this choice was to make the task equally difficult for
BG, but potentially more difficult for DI due to overlapping insets.

Nevertheless, to address all of these issues, we study dynamic inset
performance in follow-up experiment involving larger graphs of a more
realistic nature, described next.

%% ---------------------------------------------------------------------
%% EXAMPLES
%% ---------------------------------------------------------------------
\section{Examples and Follow-Up User Studies}

To showcase the applications of dynamic insets, we designed examples
for two general applications: social networks and maps.
For each application, we conducted follow-up user studies with 6
new participants recruited from the general population.
We aimed at getting feedback on the usability and effectiveness of
dynamic insets to navigate large visual spaces. 
We were also interested in studying if our navigation technique
interfered with the mental map of the participants.

\begin{table}[htb]
  \centering
  \begin{tabular}{|l|r|r|}
    \hline
    \textbf{Metric} & 
    \textbf{GeoMap} & 
    \textbf{SocNet}\\
    \hline\hline
    Efficiency (low/high) & 4.00 (0.89) & 2.83 (1.17)\\
    Enjoyability (low/high) & 4.00 (0.63) & 2.83 (0.98)\\
    Ease of use (low/high) & 4.50 (0.55) & 3.83 (0.98)\\
    Visual clutter (low/high) & 3.50 (0.84) & 4.00 (0.63)\\
    Aids mental map (no/yes) & 4.50 (0.55) & 2.67 (1.63)\\
    Context utility (low/high) & 4.67 (0.52) & 4.00 (0.82)\\
    Use in daily work? (no/yes) & 3.83 (0.75) & 2.67 (1.03)\\
    \hline
  \end{tabular}
  \caption{Subjective ratings for follow-up studies (Likert scale
    1-5 averages, standard deviations in parentheses).
    Metrics give 1-5 endpoints.}
  \label{tab:follow-up}
\end{table}

\subsection{Geographic Maps}

The inspiration for the dynamic insets technique comes from
cartography, and, not surprisingly, there is excellent potential
for using the technique for cartographic applications.
To begin realizing this potential, we have implemented a map
scenario that uses static (i.e., not live) data from Google Maps.
Figure~\ref{fig:dynamic-insets} shows a map of Chicago and its
environs.
We have modeled a connectivity graph (invisible) for a few locations
outside of the viewport; insets are automatically created for these
and laid out on the edge of the screen.   
This example clearly shows the benefit of contextual information from
the geographical features visible in the insets.

Because we are currently only modeling connectivity, and not the
actual geographical road network, insets are placed in the direction
of the destination, and not on the road.
This is a limitation of our example and not the technique itself.

Our map application is similar to existing work in cartography; for
example, Karnick et al.~\cite{Karnick2009} present a method for
visualizing route maps with multiple focus points by showing overview
and detail views of the route within a single visual frame.  
However, their goal is to provide a printable version of a route map
rather than to facilitate navigation.

\paragraph{Follow-up User Study}

We engaged 6 new participants (4 male, 2 female, all use computers
more than 16 hours/week) in a follow-up user study to perform tasks
using dynamic insets on a geographic map of the Chicago area.
This scenario lasted around 30 minutes.
All 6 participants were excited with the technique and commented in
the first few minutes how useful it would be in their everyday tasks
when navigating geographical maps.
Three of them mentioned that training was not even needed to use
dynamic insets and that navigation was ``so much easier than with
traditional zooming and scrolling.''

All participants successfully performed some 20 graph-related tasks
such as finding nodes, counting neighbors, identifying clusters,
following paths, etc.
We also asked them to revisit previously visited locations at
different stages of the exploration.
Geographical features on the map---labels, roads, cities, parks, and
water---provide very rich context and most participants explained that
after 5 minutes of exploration, they could quickly assess which part
of the map the insets were from.
We were surprised to observe almost 100\% performance in revisitation
tasks.
One participant could exactly remember the inset configurations and
found previously visited locations using long series of inset
revisitation.
This participant was also able to revisit different places using
panning when explicitly asked to do so.
Overall, these findings indicate that the technique did not interfere
with participants building mental maps of the visual space.

The center column in Table~\ref{tab:follow-up} shows subjective
ratings for the map scenario.
As the numbers show, participants rated this scenario highly and
reported how easy-to-use and enjoyable the technique was.
They did remark on the high visual clutter that arises in some
situations, and asked for a way to control the creation or filtering
of insets.
However, all six noted this as an additional desirable feature, and
not a scalability issue.

\subsection{Social Networks}

Social networks are the canonical application of graph visualization.
Using our Java framework, we implemented a simple social network
visualization and utilized our dynamic insets technique to showcase how
navigation can be improved in such networks.
Figure~\ref{fig:socnet-sparse} shows an example of this visualization
tool for the sparse condition of the randomized dataset.
In this example, the destination nodes are arranged in a radial layout
at difference distances (all outside of the viewport) from
the center node.
Because there is no overlap between any insets, all links can be
aligned with their associated insets.
Figure ~\ref{fig:socnet-dense} shows our tool with a Dense example
of social network from the controlled experiment.

\paragraph{Follow-up User Study}

The same 6 participants used a modified version of the social network
example with icons for nodes and colored node clusters in the
background of the viewport (Figure~\ref{fig:socnet-avi}).
Our dataset was the ACM AVI conference co-authorship network: a large
graph with 450 authors and approximately 1,000 edges (communicating
co-authorship), laid out using a lin-log graph layout.
We added 16 random clusters to provide some context to the network.
To ease the training and tasks, we told our participants that this
network represented friends grouped by their music preferences.
Participants were briefly instructed in how to use the technique and
then followed a task sheet to perform about 20 graph-related tasks.
The scenario lasted approximately 30 minutes.

The rightmost column in Table~\ref{tab:follow-up} shows subjective
ratings for the social network study.
Ratings are lower than for the geographical map.
We believe this is due to the fact most of our users were not familiar
with social networks; some stated they did not see why they would
perform such tasks at all.
In other words, their motivation to use our technique in this scenario
was low.
In addition, the network proposed was much larger and denser than in
the map scenario, making tasks more difficult to complete, and,
despite getting a break, participants reported fatigue from their
previous exploration.

Despite these lower ratings, our participants performed very well with
dynamic insets, indicating that the technique scales to larger graphs.
All participants were able to accurately perform all tasks, including
spatial memory tasks (navigating to specific communities or nodes).
We were surprised that users were able to memorize the location of
specific communities after such a short exploration time and the lack
of distinctive spatial features compared to the map scenario.
This observation further indicates that dynamic insets do not
interfere with the creation of a mental map.
While all participants were able to perform tasks in very cluttered
areas (up to 25 insets on the screen edge), they suggested again that
filters would allow them to better control which insets to show.
Nevertheless, all participants used either the fanning, panning or the paging
technique in solving tasks.

\begin{figure}[htb]
  \centering
  \resizebox{\columnwidth}{!}{\includegraphics{figures/socnet-avi}}
    \caption{Social network for the ACM AVI co-authorship dataset.
    This is the application we used in one of the follow-up user
    studies.}
  \label{fig:socnet-avi}
\end{figure}

%% ---------------------------------------------------------------------
%% CONCLUSION
%% ---------------------------------------------------------------------
\section{Conclusion and Future Work}

We have presented a context-aware graph navigation technique that
utilizes the topology of a graph to dynamically create insets for
off-screen neighbors of visible nodes.
We give two examples showcasing the utility of the technique for
social networks and geographical maps.
We also present results from a controlled experiment that shows that
our technique outperforms current state-of-the-art graph navigation
techniques, as well as more qualitative findings from two usability
studies with larger and more realistic tasks.

In our future endeavors we want to study the performance of different
distance and degree-of-interest mechanisms. 
We also plan to deploy the technique in a real-world online map
website such as Google Maps or Bing Maps.

%% Acknowledgements (omitted in review mode)
%\acknowledgements{We would like to thank the anonymous participants
%  that participated in our experiment.}

% ----------------------------------------------------------------------
% Bibliography
% ----------------------------------------------------------------------
\bibliographystyle{abbrv}
\bibliography{dyninsets}

\end{document}
